This invention relates to the general area of first-in-first-out (FIFO) register sets as used in the computing field to communicate between apparatus operating at different rates. More particularly it relates to asynchronous FIFOs in which data signals are transferred bidirectionally inside the FIFO without regard to system clocks, but rather at a speed determined entirely by the speed of the circuitry within the FIFO. The asynchronous design of the FIFO permits it to operate at the maximum speed of which its circuitry is capable.
In a broad sense, first-in-first-out storage systems are familiar in a wide variety of applications. In manufacturing production lines, for example, FIFO storage holds work-in-process to provide a buffer between two operating stations on the line, allowing the stations to function somewhat independently.
In computing equipment, electronic digital first-in-first-out storage systems serve in a similar capacity. Just as in a production line, these electronic units, called FIFOs, buffer independent processes. A FIFO stores the output from one process until a subsequent processor is ready for it. The first-in-first-out nature of FIFO storage systems ensures that the subsequent processor receives the data elements in the same order that they were generated, though not necessarily on the same time schedule.
FIFO storage systems are used in computers, just as they are used in production line manufacturing processes, to provide time independence between the processing operations preceding and following the FIFO. The FIFO decouples the processor before it from the one after it. Accordingly, it can deliver data to a later processor even if the earlier process has temporarily halted. Similarly, a FIFO can hold the output from a preceding processor while a later processor is temporarily unable to accept input.
If two computing processors operate in pipeline fashion at different instantaneous rates, a FIFO is required between them. Data from one processor, e.g. the head of a magnetic storage disk, will enter the FIFO at a rate determined by the source process. Specifically, data from the storage disk will enter the FIFO at a rate set by the rotation rate of the disk and the bit density of the data storage on the disk. Also, the data flow will be interrupted periodically by inter-record gaps. Normally, the data will be delivered to another processor, e.g. a computer, at a rate suitable for its operation. The FIFO serves as a buffer between the two processors. It permits each of the processors to deliver or obtain data at a rate convenient to it, without regard to the instantaneous speed or timing of the other processor. Thus, a FIFO couples two processors with regard to work flow, but decouples their timing.
Clocking within a traditional FIFO can be a complex matter. Most computing systems are built with clocked logic. Each step in the process proceeds according to the beat of the clock; identical clock signals are delivered to all parts of the system, just as an identical drum beat is delivered to all men in a marching column. Within the purview of the prior art, it is relatively simple to build FIFOs for use between two processors if both use the same clock. In the same context, it is a more difficult problem to build a FIFO suitable for use between two processors with independent clocks. Such a FIFO must accommodate not only irregularities in the availability of data, but also the differences in the basic clocking systems. Thus, in traditional FIFOs the form of clock used within a FIFO is an important design factor.
The nature of the clock used within some conventional FIFOs is critical to performance. Some prior hardware FIFO systems, and essentially all prior FIFOs implemented in software, operate internally in a synchronous manner. That is, in the case of hardware, timing is dictated by the beat of the clock. In the case of software, timing is at the pace of the instructions executed.
While synchronous FIFOs are most suitable for coupling processors that share a common clock, other systems are not so well handled and demand asynchronous operation. Accordingly, different parts of the FIFO must perform their operations whenever local conditions permit.
This invention involves an asynchronous FIFO in which each part of the FIFO operates independently. Because of its asynchronous design, the FIFO of the present invention can be used to couple processors with a common clock or processors that operate independently with respect to time. The system is particularly suitable for coupling asynchronous units that are able to make use of the asynchronous protocol described here which is available at both the input and the output of the FIFO.
Generally, in an asynchronous sequential FIFO, data elements enter an input port and move sequentially and asynchronously through an array of data cells to an output port from which they emerge in the same order as they entered. Each element moves forward as far and as fast as it can, with due regard to avoiding destruction of the data element ahead of it in the sequence. An asynchronous sequential FIFO is distinguished from a synchronous sequential FIFO by the fact that different data elements move at different times, and not in synchrony with a common clock. The control element for each data cell in an asynchronous sequential FIFO need consider only the state of its predecessor and successor cells and can remain ignorant of other global conditions.
The local control of the elements in an asynchronous sequential FIFO is well suited to modern integrated circuit implementations, for in such a design, signal wires can be as short as the separation of adjacent data cells and will therefore have much lower electrical capacity than would longer wires. The short wires permit the data cells to consume very low power and still operate at high speed. Local control is also advantageous in large systems where the delivery of a clock signal to many independent cells is difficult and clock "skew" is a problem.
Two kinds of local control can be used in asynchronous sequential systems. According to one kind of control, the same wires that carry data signals from one cell to the next also carry control information. Such mechanisms are usually designed for systems that carry data elements each of which contains only a single bit. Such a one-bit asynchronous sequential system with data and control carried on the same wires is called a "QUEUE". QUEUEs can also be designed to carry multiple bit data elements, but substantially more logic is required.
In the other kind of asynchronous sequential system, the data moves through its data cells under control of a separate control mechanism. In these systems, more generally called FIFOs rather than QUEUEs, one or more control wires, generally two, are placed in parallel with the data wires. The control wires carry signals indicating whether data can move into the next successive data location, and whether it actually has moved. The present disclosed embodiment is an asynchronous sequential FIFO with control signals separate from data signals.
Asynchronous sequential FIFOs with separate control and data generally consist of two main parts. The first part is a data unit that contains a sequence of identical data cells. The data cells pass data from cell to cell en route from the FIFO input to output. The second part of such a FIFO is a control unit that contains a sequence of identical control elements that control the actions of the data cells. Each control element controls one or more data cells. Asynchronous sequential FIFOs are distinguished by the form and interconnections of their data cells and by the form and interconnections of their control elements. Because the data unit and the control unit normally are composed of a sequence of identical cells or elements respectively, one might describe a FIFO by describing the properties of a single data cell, the properties of a single control element, and the connections between them.
The data paths used in traditional FIFO systems share three characteristics. First, each data register is a distinct entity. Usually each such register is composed of two inverters or two inverting logic gates connected back to back so as to form a flip-flop of the kind in common use and familiar to those skilled in the art. Each of the gates in the flip flop is always associated with the other; the two gates are joined irrevocably as a pair defining a flip flop.
The second common characteristic of traditional FIFOs is that all data cells are connected to their respective control elements in the same way. Thus, except for their order within the FIFO, all data cells are interchangeable in a logical sense.
A third common characteristic of traditional FIFOs is that any given control signal must go through a complete cycle of two transitions for each step in the operation of the FIFO. Thus, for example, in known FIFOs, data moves forward into a particular stage only during the period when its control signal is in one logical state, say the TRUE state. Thus, to move a datum requires that the control system cycle from FALSE to TRUE and back to FALSE again, which requires two logical transitions of the control element.